package cn.bellychang.wangzheng.backtracking;

/**
 * @author ChangLiang
 * @date 2021/2/19
 */
public class Cal8QueensSolution {

    /**
     * 下标表示行 值表示queen存储在哪一列
     */
    int[] result = new int[8];

    int num = 0;

    public void cal8Queens(int row) {
        if (row == 8) {
            // 8个棋子都放好了 打印结果
            printQueens(result);
            // 8个棋子都放好了 无法再向下递归了 return
            return;
        }
        for (int column = 0; column < 8; column++) {
            if (isOk(row, column)) {
                // 将第row行的棋子放到了column列
                result[row] = column;
                // 考察下一行
                cal8Queens(row+1);
            }
        }
    }

    /**
     * 判断row行 column列放置是否合适
     * @param row
     * @param column
     * @return
     */
    private boolean isOk(int row, int column) {

        int leftup = column - 1;
        int rightup = column + 1;
        for (int i = row - 1; i >=0; i--) {
            // 逐行向上考察每一行
            if (result[i] == column) {
                // 第i行的column列有棋子吗
                return false;
            }
            if (leftup >= 0) {
                // 考察左上对角线：第i行 leftup列有棋子吗
                if (result[i] == leftup) {
                    return false;
                }
            }
            if (rightup < 8) {
                // 考察右上对角线：第i行 rightup列有棋子吗
                if (result[i] == rightup) {
                    return false;
                }
            }
            leftup--;
            rightup++;
        }
        return true;
    }

    /**
     * 打印一个二维矩阵
     * @param result
     */
    private void printQueens(int[] result){

        for (int row = 0; row < 8; row++) {
            for (int column = 0; column < 8; column++) {
                if (result[row] == column) {
                    System.out.print("Q ");
                } else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        num++;
        System.out.println(" solution No. #" + num);
    }
}
